home *** CD-ROM | disk | FTP | other *** search
/ ftp.mactech.com 2010 / ftp.mactech.com.tar / ftp.mactech.com / challenge / 13.08 / ChallengeEqEval.sit.hqx / Challenge, Equation Evaluator / CodeGen.c < prev    next >
Text File  |  1997-06-25  |  22KB  |  753 lines
  1. //
  2. //    CodeGen.c
  3. //
  4. //    MacTech Programmer's Challenge entry for May, 1997
  5. //    Written by Mark Day
  6. //
  7. //    Contains various routines used to produce PowerPC object code
  8. //    (in memory) to evaluate an equation at a range of input values.
  9. //
  10.  
  11.  
  12. #include <Memory.h>
  13. #include "Evaluate.h"
  14.  
  15. //
  16. //    Some simple macros for producing the PowerPC instructions in the generated
  17. //    code.  The order of the arguments matches the order you'd write those arguments
  18. //    in assembly language source.
  19. //
  20.  
  21. #define op_add(rD, rA, rB)        (0x7C000214 + (rD<<21) + (rA<<16) + (rB<<11))
  22. #define op_addi(rD, rA, simm)    (0x38000000 + (rD<<21) + (rA<<16) + (simm & 0xFFFF))
  23. #define op_b(offset)            (0x48000000 + (offset & 0x03FFFFFC))
  24. #define op_bctr()                (0x4e800420)
  25. #define op_bl(offset)            (0x48000001 + (offset & 0x03FFFFFC))
  26. #define op_blr()                (0x4e800020)
  27. #define op_bne(offset)            (0x40820000 + (offset & 0xFFFF))
  28. #define op_cmplwi(rA, uimm)        (0x28000000 + (rA<<16) + (uimm & 0xFFFF))
  29. #define op_fabs(frD, frB)        (0xFC000210 + (frD<<21) + (frB<<11))
  30. #define op_fadds(frD, frA, frB)    (0xEC00002A + (frD<<21) + (frA<<16) + (frB<<11))
  31. #define op_fdivs(frD, frA, frB)    (0xEC000024 + (frD<<21) + (frA<<16) + (frB<<11))
  32. #define op_fmadds(frD, frA, frC, frB) (0xEC00003A + (frD<<21) + (frA<<16) + (frB<<11) + (frC<<6))
  33. #define op_fmr(frD, frS)        (0xFC000090 + (frD<<21) + (frS<<11))
  34. #define op_fmuls(frD, frA, frC)    (0xEC000032 + (frD<<21) + (frA<<16) + (frC<<6))
  35. #define op_fneg(frD, frB)        (0xFC000050 + (frD<<21) + (frB<<11))
  36. #define op_fsubs(frD, frA, frB)    (0xEC000028 + (frD<<21) + (frA<<16) + (frB<<11))
  37. #define op_lfs(frD, d, rA)        (0xC0000000 + (frD<<21) + (rA<<16) + d)
  38. #define op_lwz(rD, d, rA)        (0x80000000 + (rD<<21) + (rA<<16) + d)
  39. #define op_mflr(rD)                (0x7c0802a6 + (rD<<21))
  40. #define op_mtctr(rS)            (0x7c0903a6 + (rS<<21))
  41. #define op_mtlr(rS)                (0x7c0803a6 + (rS<<21))
  42. #define op_nop()                (0x60000000)
  43. #define op_stfs(frS, d, rA)        (0xD0000000 + (frS<<21) + (rA<<16) + d)
  44. #define op_stfsu(frS, d, rA)    (0xD4000000 + (frS<<21) + (rA<<16) + d)
  45. #define op_stwu(rS, d, rA)        (0x94000000 + (rS<<21) + (rA<<16) + d)
  46. #define op_subi(rD, rA, simm)    op_addi(rD, rA, -simm)
  47.  
  48.  
  49. /*
  50.     Some missing optimizations:
  51.         • Loop unrolling (** probably the most imporant opportunity **)
  52.         • Common sub-expression elimination
  53.             • Example: It's usually faster to compute both cos(x) and sin(x)
  54.                        in a single operation than computing them separately.
  55.                        The trick is recognizing the opportunity; CSE is a start.
  56.         • Take advantage of trig identities
  57.         • Redundant load/store
  58.         • Sometimes moves values to and from non-volatile storage when the
  59.                 intervening operations don't change volatile registers.
  60.         • Doesn't combine multiply and add into a single instruction.
  61.         • Negation should be combined with previous fmul or fabs instruction.
  62. */
  63.  
  64. ulong regUsage[32];        // non-zero means register[x] is currently in use
  65. ulong numMemoryVars;    // number of temporaries not in registers
  66. ulong gNumConstants;
  67. float *gConstants = NULL;
  68. ulong *gCodeBase;
  69. ulong *gNextInstruction;
  70.  
  71. void InitCodeGen(ulong *codeStart)
  72. {
  73.     int i;
  74.     
  75.     gCodeBase = codeStart;
  76.     gNextInstruction = codeStart;
  77.     
  78.     for (i=0; i<32; i++)
  79.         regUsage[i] = 0;        // mark registers as not in use (i.e. available)
  80.     numMemoryVars = gNumConstants;    // put constants in overflow register pool
  81.     
  82.     //
  83.     //    For variables that are used, mark them
  84.     //
  85.     if (gVariableFlags & kNMask)
  86.         regUsage[regN] = 1;
  87.     if (gVariableFlags & kXMask)
  88.         regUsage[regX] = 1;
  89.     if (gVariableFlags & kYMask)
  90.         regUsage[regY] = 1;
  91.     if (gVariableFlags & kRMask)
  92.         regUsage[regR] = 1;
  93.     if (gVariableFlags & kThetaMask)
  94.         regUsage[regTheta] = 1;
  95.     if (gVariableFlags & kEMask)
  96.         regUsage[regE] = 1;
  97.     if (gVariableFlags & kPiMask)
  98.         regUsage[regPi] = 1;
  99.     
  100.     //
  101.     //    Allocate memory for constants
  102.     //
  103.     gConstants = (float *) NewPtr(gNumConstants * sizeof(float));
  104.     gNumConstants = 0;
  105. }
  106.  
  107. //
  108. //    AllocateRegister: reserve a non-volatile register or memory location
  109. //    to hold some value.
  110. //
  111. static ulong AllocateRegister(void)
  112. {
  113.     int i;
  114.     
  115.     //
  116.     //    Try allocating a real register.
  117.     //
  118.     for (i=regFreeBase; i<regMax; i++) {
  119.         if (regUsage[i] == 0) {
  120.             ++regUsage[i];
  121.             return i;
  122.         }
  123.     }
  124.     
  125.     //
  126.     //    Didn't work.  Need to use memory.
  127.     //
  128.     return regMemory + numMemoryVars++;
  129. }
  130.  
  131. //
  132. //    UseRegister: Mark a register as in use.  If the given register
  133. //    is a non-volatile register (not a memory location), then increment
  134. //    it's usage count.  This is similar to AllocateRegister, but when
  135. //    you already have the register number.
  136. //
  137. static void UseRegister(ulong which)
  138. {
  139.     if (which >= regFreeBase && which < regMax) {
  140.         ++regUsage[which];
  141.     }
  142. }
  143.  
  144. //
  145. //    FreeRegister: Mark a register or memory location as available
  146. //    for use again.  If the register is volatile or a memory location,
  147. //    don't do anything.
  148. //
  149. static void FreeRegister(ulong which)
  150. {
  151.     if (which >= regFreeBase && which < regMax) {
  152.         --regUsage[which];
  153.     }
  154. }
  155.  
  156. //
  157. //    LoadRegister: Make sure the source register/memory is in a real
  158. //    register.  If not, move it to the destination (which is a real
  159. //    register) via a lfs instruction.
  160. //
  161. static ulong LoadRegister(ulong source, ulong destination)
  162. {
  163.     ulong    displacement;
  164.     
  165.     if (source >= regMemory) {
  166.         displacement = (source-regMemory)*4;
  167.         *(gNextInstruction++) = op_lfs(destination, displacement, regVariableBase);
  168.  
  169.         return destination;
  170.     }
  171.     else {
  172.         return source;
  173.     }
  174. }
  175.  
  176. //
  177. //    StoreRegister: Store a register in memory.  Source must
  178. //    be a real register.  Destination must be memory.
  179. //
  180. static void StoreRegister(ulong destination, ulong source)
  181. {
  182.     ulong    displacement;
  183.     
  184.     if (destination < regMemory) {
  185.         return;
  186.     }
  187.     if (source >= regMax) {
  188.         return;
  189.     }
  190.     
  191.     displacement = (destination-regMemory)*4;
  192.     *(gNextInstruction++) = op_stfs(source, displacement, regVariableBase);
  193.     
  194. }
  195.  
  196. //
  197. //    TemporaryResult: Generate a (real) register number to be a destination register
  198. //    for some instruction.  The destination has already been determined and is in "which".
  199. //    If "which" is memory, then use a volatile register, which will be stored later.
  200. //
  201. static ulong TemporaryResult(ulong which)
  202. {
  203.     if (which >= regMemory)
  204.         return fpTempResult;
  205.     else
  206.         return which;
  207. }
  208.  
  209. //
  210. //    StoreResult: the second part of TemporaryResult.  If TemporaryResult was passed
  211. //    a memory location, then this function takes care of actually storing the result
  212. //    (after it has been put in the temporary volatile register).
  213. //
  214. static void StoreResult(ulong which)
  215. {
  216.     if (which >= regMemory) {
  217.         StoreRegister(which, fpTempResult);
  218.     }
  219. }
  220.  
  221. //
  222. //    MoveRegister: Move register to memory, register to register, or memory to register.
  223. //
  224. static void MoveRegister(ulong destination, ulong source)
  225. {
  226.     if (source >= regMax) {
  227.         //    Source is memory.
  228.         if (destination < regMax)
  229.             LoadRegister(source, destination);
  230.         
  231.         return;
  232.     }
  233.     
  234.     if (destination >= regMax) {
  235.         //    Destination is in memory, so generate a stfs instruction
  236.         StoreRegister(destination, source);
  237.     }
  238.     else {
  239.         //    Source and destination are registers, so generate fmr instruction
  240.         *(gNextInstruction++) = op_fmr(destination, source);
  241.     }
  242. }
  243.  
  244. //
  245. //    NonVolatileRegister: Makes sure a value is in a non-volatile location.
  246. //    If source is already a non-volatile register or memory, then just use it.
  247. //    Otherwise, store the volatile register in a newly allocated register or
  248. //    memory and return the new location.
  249. //
  250. static ulong NonVolatileRegister(ulong source)
  251. {
  252.     ulong    destination;
  253.     
  254.     if (source < regFreeBase) {
  255.         destination = AllocateRegister();
  256.         MoveRegister(destination, source);
  257.         return destination;
  258.     }
  259.     else {
  260.         return source;
  261.     }
  262. }
  263.  
  264. //
  265. //    CallFunction: Call a function.  Put the descriptor pointer into R12 and
  266. //    use the function call glue at 0 to jump to the desired routine.
  267. //
  268. static void CallFunction(ulong which)
  269. {
  270.     long    displacement;
  271.     
  272.     //
  273.     //    Load the pointer to the desired function into r12
  274.     //
  275.     displacement = which*4;
  276.     *(gNextInstruction++) = op_lwz(regFunctionGlue, displacement, regFunctionBase);
  277.  
  278.     //
  279.     //    Generate a bl instruction to the glue at the start of the generated code.
  280.     //
  281.     displacement = (ulong) gCodeBase - (ulong) gNextInstruction;
  282.     *(gNextInstruction++) = op_bl(displacement);
  283. }
  284.  
  285.  
  286. /*
  287.     CodeGen
  288.     
  289.     Inputs:
  290.         root            (sub)tree to generate code for
  291.         resultRegister    desired register for result (0 = any)
  292.     
  293.     Result:
  294.         Register containing result.  If resultRegister was non-zero, then
  295.         this will be the same as resultRegister.
  296. */
  297.  
  298.  
  299.  
  300. int CodeGenTree(TokenNode *root, int resultRegister)
  301. {
  302.     char    *opname;
  303.     ulong    temp, temp2;
  304.     ulong    arg1, arg2;
  305.     int    result;
  306.     
  307.     if (root == NULL) {
  308.         return 0;
  309.     }
  310.     
  311.     switch (root->token) {
  312.         case tokFloat:
  313.             //
  314.             //    Stuff the constant in memory in the first part of the overflow
  315.             //    register area.
  316.             //
  317.             gConstants[gNumConstants] = root->value.f;
  318.             
  319.             //
  320.             //    If the result needs to go into a specific register, then
  321.             //    load that register from memory.  Otherwise, return an overflow
  322.             //    register number (which will get loaded into a temporary register
  323.             //    just before being used).
  324.             //
  325.             
  326.             if (resultRegister) {
  327.                 //    Explicitly move value to a given register
  328.                 result = resultRegister;
  329.                 LoadRegister(regMemory + gNumConstants, resultRegister);
  330.             }
  331.             else {
  332.                 //    Tell caller where the value is so they can fetch it
  333.                 result = regMemory + gNumConstants;
  334.             }
  335.             
  336.             gNumConstants++;
  337.             return result;
  338.  
  339.         case tokAddOp:
  340.             temp = CodeGenTree(root->left, 0);
  341.             temp = NonVolatileRegister(temp);        //    make sure it's in a non-volatile reg.
  342.             temp2 = CodeGenTree(root->right, 0);    //    so we can evaluate second arg
  343.             
  344.             FreeRegister(temp);
  345.             FreeRegister(temp2);
  346.             
  347.             if (resultRegister)
  348.                 result = resultRegister;
  349.             else
  350.                 result = AllocateRegister();
  351.             
  352.             arg1 = LoadRegister(temp, fpTemp1);
  353.             arg2 = LoadRegister(temp2, fpTemp2);
  354.             
  355.             if (root->value.which == kAdd) {
  356.                 *(gNextInstruction++) = op_fadds(TemporaryResult(result), arg1, arg2);
  357.             }
  358.             else {
  359.                 *(gNextInstruction++) = op_fsubs(TemporaryResult(result), arg1, arg2);
  360.             }
  361.  
  362.             StoreResult(result);
  363.             return result;
  364.  
  365.         case tokMulOp:
  366.             temp = CodeGenTree(root->left, 0);
  367.             temp = NonVolatileRegister(temp);        //    make sure it's in a non-volatile reg.
  368.             temp2 = CodeGenTree(root->right, 0);    //    so we can evaluate second arg
  369.             
  370.             FreeRegister(temp);
  371.             FreeRegister(temp2);
  372.             
  373.             if (resultRegister)
  374.                 result = resultRegister;
  375.             else
  376.                 result = AllocateRegister();
  377.  
  378.             arg1 = LoadRegister(temp, fpTemp1);
  379.             arg2 = LoadRegister(temp2, fpTemp2);
  380.             
  381.             if (root->value.which == kMultiply) {
  382.                 *(gNextInstruction++) = op_fmuls(TemporaryResult(result), arg1, arg2);
  383.             }
  384.             else {
  385.                 *(gNextInstruction++) = op_fdivs(TemporaryResult(result), arg1, arg2);
  386.             }
  387.  
  388.             StoreResult(result);
  389.             return result;
  390.  
  391.         case tokPowerOp:
  392.             //    Evaluate second argument, put in any register.
  393.             temp = CodeGenTree(root->right, 0);
  394.             temp = NonVolatileRegister(temp);        //    make sure it's in a non-volatile reg.
  395.             
  396.             //    Evaluate first argument, put into fpArg1.
  397.             CodeGenTree(root->left, fpArg1);
  398.             
  399.             //    Move second argument to fpArg2
  400.             //    If first argument didn't require a function call, we could have
  401.             //    put second argument directly into fpArg2
  402.             MoveRegister(fpArg2, temp);
  403.             
  404.             FreeRegister(temp);
  405.             
  406.             //    Call power function
  407.             CallFunction(kFuncPower);
  408.             
  409.             //    Return result in desired register
  410.             temp = fpResult;
  411.             if (resultRegister && resultRegister != temp) {
  412.                 MoveRegister(resultRegister, temp);
  413.                 temp = resultRegister;
  414.             }
  415.             
  416.             return temp;
  417.  
  418.         case tokNegate:
  419.             temp = CodeGenTree(root->left, 0);
  420.             FreeRegister(temp);
  421.             
  422.             if (resultRegister)
  423.                 result = resultRegister;
  424.             else
  425.                 result = AllocateRegister();
  426.  
  427.             arg1 = LoadRegister(temp, fpTemp1);
  428.             
  429.             *(gNextInstruction++) = op_fneg(TemporaryResult(result), arg1);
  430.  
  431.             StoreResult(result);
  432.             return result;
  433.  
  434.         case tokAbs:
  435.             temp = CodeGenTree(root->left, 0);
  436.             FreeRegister(temp);
  437.             
  438.             if (resultRegister)
  439.                 result = resultRegister;
  440.             else
  441.                 result = AllocateRegister();
  442.  
  443.             arg1 = LoadRegister(temp, fpTemp1);
  444.             
  445.             *(gNextInstruction++) = op_fabs(TemporaryResult(result), arg1);
  446.  
  447.             StoreResult(result);
  448.             return result;
  449.  
  450.         case tokFunction:
  451.             //    Evaluate the argument (root->left), putting it
  452.             //    in fp1.
  453.             temp = CodeGenTree(root->left, fpArg1);
  454.             
  455.             //
  456.             //    Call the function
  457.             //
  458.             CallFunction(root->value.which);
  459.             
  460.             //
  461.             //    Put the result in the desired location
  462.             //
  463.             temp = fpResult;
  464.             if (resultRegister && resultRegister != temp) {
  465.                 MoveRegister(resultRegister, temp);
  466.                 temp = resultRegister;
  467.             }
  468.             
  469.             return temp;
  470.  
  471.         case tokVariable:
  472.             switch (root->value.which) {
  473.                 case kPi:
  474.                     temp = regPi;
  475.                     break;
  476.                 case kE:
  477.                     temp = regE;
  478.                     break;
  479.                 case kR:
  480.                     temp = regR;
  481.                     break;
  482.                 case kTheta:
  483.                     temp = regTheta;
  484.                     break;
  485.                 case kX:
  486.                     temp = regX;
  487.                     break;
  488.                 case kY:
  489.                     temp = regY;
  490.                     break;
  491.                 case kN:
  492.                     temp = regN;
  493.                     break;
  494.             }
  495.             
  496.             if (resultRegister && resultRegister != temp) {
  497.                 MoveRegister(resultRegister, temp);
  498.                 temp = resultRegister;
  499.             }
  500.  
  501.             UseRegister(temp);        // balance FreeRegister when this value is used
  502.             return temp;
  503.  
  504.         default:
  505.             //    Should never get here.
  506.             return 0;
  507.     }
  508.     
  509.     //    Should never get here.
  510.     return 0;
  511. }
  512.  
  513.  
  514.  
  515. //
  516. //    If r or theta (t) is used to evaluate the equation, generate some code
  517. //    to set up their values based on the values of x and y.
  518. //
  519. static void CodeGenRTheta(void)
  520. {
  521.     if (gVariableFlags & kRMask) {
  522.         //    r = sqrtf(x*x + y*y)
  523.         *(gNextInstruction++) = op_fmuls(fpArg1, regX, regX);
  524.         *(gNextInstruction++) = op_fmadds(fpArg1, regY, regY, fpArg1);
  525.         CallFunction(kFuncSquareRoot);
  526.         MoveRegister(regR, fpResult);
  527.     }
  528.     
  529.     if (gVariableFlags & kThetaMask) {
  530.         //    theta = atan2f(x,y)
  531. // CORRECTION by JRB, should be theta = atan2f(y,x)
  532. #if 0
  533.         MoveRegister(fpArg1, regX);
  534.         MoveRegister(fpArg2, regY);
  535. #else
  536.         MoveRegister(fpArg1, regY);
  537.         MoveRegister(fpArg2, regX);
  538. #endif
  539. // END CORRECTION
  540.         CallFunction(kFuncAtan2);
  541.         MoveRegister(regTheta, fpResult);
  542.     }
  543. }
  544.  
  545.  
  546. //
  547. //    Generate code to store one equation result plus the variables
  548. //    used to produce that result.  Assumes that the wP register points
  549. //    to 4 bytes BEFORE the location to start storing (so we can use the
  550. //    store-with-update instructions).
  551. //
  552. static void CodeGenStoreResult(ulong result)
  553. {
  554.     //    Store equation result
  555.     *(gNextInstruction++) = op_stfsu(result, 4, regResults);
  556.  
  557.     //    Store x
  558.     *(gNextInstruction++) = op_stfsu(regX, 4, regResults);
  559.  
  560.     if (gVariableFlags & kFunctionOfY) {
  561.         //    Store both y and n
  562.         *(gNextInstruction++) = op_stfsu(regY, 4, regResults);
  563.         *(gNextInstruction++) = op_stwu(regNInteger, 4, regResults);
  564.     }
  565.     else {
  566.         //    Skip over y and store n
  567.         *(gNextInstruction++) = op_stwu(regNInteger, 8, regResults);
  568.     }
  569. }
  570.  
  571.  
  572.  
  573. //
  574. //    Generate code to initialize the loop variables.
  575. //    Load the first value, load the count (howMany), then branch
  576. //    to the test part of the loop (after the body of the loop).
  577. //    Since we don't know where the test will be, we just skip an
  578. //    instruction word and will insert the branch when we generate
  579. //    the test.
  580. //
  581. static void CodeGenLoopInit(ulong variableFlags, ulong **xBranch, ulong **yBranch, ulong **nBranch)
  582. {
  583.     //    Generate the loop for x first
  584.     if (variableFlags & kXMask) {
  585.         *(gNextInstruction++) = op_lfs(regX, 0, regXValues);        // x = xP->first
  586.         *(gNextInstruction++) = op_lwz(regXCount, 8, regXValues);    // xCount = xP->howMany
  587.         *xBranch = gNextInstruction;                                // remember branch address
  588.         *(gNextInstruction++) = op_nop();                            // will be patched later
  589.     }
  590.     
  591.     //    Now generate the loop for y, if function was of the form "z=..."
  592.     if ((variableFlags & kFunctionOfY) && (variableFlags & kYMask)) {
  593.         *(gNextInstruction++) = op_lfs(regY, 0, regYValues);        // y = yP->first
  594.         *(gNextInstruction++) = op_lwz(regYCount, 8, regYValues);    // yCount = yP->howMany
  595.         *yBranch = gNextInstruction;
  596.         *(gNextInstruction++) = op_nop();        // will be patched later
  597.     }
  598.     
  599.     //    And lastly, n.  N is a bit different since we maintain
  600.     //    both the integer and floating point values simultaneously.
  601.     if (variableFlags & kNMask) {
  602.         *(gNextInstruction++) = op_lfs(regN, 0, regNValues);            // n = nFloat->first
  603.         *(gNextInstruction++) = op_lwz(regNInteger, 0, regNIntValues);    // nInteger = nP->first
  604.         *(gNextInstruction++) = op_lwz(regNCount, 8, regNIntValues);    // nCount = nP->howMany
  605.         *nBranch = gNextInstruction;
  606.         *(gNextInstruction++) = op_nop();                                // will be patched later
  607.     }
  608. }
  609.  
  610.  
  611.  
  612. //
  613. //    Generate the iteration step and test/branch for the variable loops.
  614. //    Just before we generate the test/branch instructions, patch up the
  615. //    branch instructions inserted by CodeGenLoopInit.
  616. //
  617. //    The general form generates something like:
  618. //    iteration:        x += xP->delta;
  619. //                    xCount--;
  620. //    test:            if (xCount != 0) goto loop_body
  621. //
  622. //    where loop_body is the instruction following the forward branch that gets patched.
  623. //
  624. static void CodeGenLoopEnd(ulong variableFlags, ulong *xBranch, ulong *yBranch, ulong *nBranch)
  625. {
  626.     ulong    offset;
  627.     
  628.     //    Generate the part for n.  Remember that we must increment both the integer
  629.     //    and floating point values of n.
  630.     if (variableFlags & kNMask) {
  631.         *(gNextInstruction++) = op_lfs(fpTemp1, 4, regNValues);    //    get nFloatValues->delta
  632.         *(gNextInstruction++) = op_fadds(regN, regN, fpTemp1);    //    increment n (float)
  633.         *(gNextInstruction++) = op_lwz(regIntTemp1, 4, regNIntValues);    //    get nP->delta
  634.         *(gNextInstruction++) = op_add(regNInteger, regNInteger, regIntTemp1);    //    increment n
  635.         *(gNextInstruction++) = op_subi(regNCount, regNCount, 1);    //    nCount--
  636.         offset = (int) gNextInstruction - (int) nBranch;
  637.         *nBranch = op_b(offset);                                //    patch branch at start of loop
  638.         *(gNextInstruction++) = op_cmplwi(regNCount, 0);        //    nCount == 0?
  639.         offset = (int) (nBranch+1) - (int) gNextInstruction;
  640.         *(gNextInstruction++) = op_bne(offset);                    //    if not, branch to loop body
  641.     }
  642.     
  643.     //    Next comes y, if a loop was generated for it (i.e. equation was "z=...")
  644.     if ((variableFlags & kFunctionOfY) && (variableFlags & kYMask)) {
  645.         *(gNextInstruction++) = op_lfs(fpTemp1, 4, regYValues);    //    get yP->delta
  646.         *(gNextInstruction++) = op_fadds(regY, regY, fpTemp1);    //    increment y
  647.         *(gNextInstruction++) = op_subi(regYCount, regYCount, 1);    //    yCount--
  648.         offset = (int) gNextInstruction - (int) yBranch;
  649.         *yBranch = op_b(offset);                                //    patch branch at start of loop
  650.         *(gNextInstruction++) = op_cmplwi(regYCount, 0);        //    yCount == 0?
  651.         offset = (int) (yBranch+1) - (int) gNextInstruction;
  652.         *(gNextInstruction++) = op_bne(offset);                    //    if not, branch to loop body
  653.     }
  654.  
  655.     //    
  656.     //    Lastly comes x.
  657.     //
  658.     if (variableFlags & kXMask) {
  659.         *(gNextInstruction++) = op_lfs(fpTemp1, 4, regXValues);    //    get xP->delta
  660.         *(gNextInstruction++) = op_fadds(regX, regX, fpTemp1);    //    increment x
  661.         *(gNextInstruction++) = op_subi(regXCount, regXCount, 1);    //    xCount--
  662.         offset = (int) gNextInstruction - (int) xBranch;
  663.         *xBranch = op_b(offset);                                //    patch branch at start of loop
  664.         *(gNextInstruction++) = op_cmplwi(regXCount, 0);        //    xCount == 0?
  665.         offset = (int) (xBranch+1) - (int) gNextInstruction;
  666.         *(gNextInstruction++) = op_bne(offset);                    //    if not, branch to loop body
  667.     }
  668. }
  669.  
  670.  
  671. //
  672. //    Build up a function that loops over all the variable input values, evaluates
  673. //    the function, and stores the results.
  674. //
  675. //    If the loops were written in C, they'd look like this:
  676. //        for (x=xP->first, xCount=xP->howMany;        // loop initialization
  677. //             xCount != 0;                            // loop condition
  678. //             x+=xP->delta, xCount--)                // iteration step
  679. //        {
  680. //            evaluate and store the result
  681. //        }
  682. //
  683.  
  684. void CodeGen(TokenNode *root)
  685. {
  686.     ulong    result;
  687.     ulong    *generatedCode;
  688.     ulong    *xBranch, *yBranch, *nBranch;
  689.     
  690.     generatedCode = (ulong *) NewPtr(32768);
  691.  
  692.     if (generatedCode != NULL) {
  693.         InitCodeGen(generatedCode);
  694.         
  695.         //
  696.         //    Generate the pointer glue for making indirect function calls
  697.         //
  698.         *(gNextInstruction++) = op_lwz(regR0, 0, regFunctionGlue);    // lwz r0, 0(r12)
  699.         *(gNextInstruction++) = op_lwz(regTOC, 4, regFunctionGlue);    // lwz r2, 4(r12)
  700.         *(gNextInstruction++) = op_mtctr(regR0);                    // mtcr r0
  701.         *(gNextInstruction++) = op_bctr();                            // bctr
  702.         
  703.         //
  704.         //    Generate the function prolog -- save the link register
  705.         //
  706.         *(gNextInstruction++) = op_mflr(regSavedLR);                // mflr r15
  707.         
  708.         //
  709.         //    Generate loop initialization for any variables that _are_
  710.         //    used to evaluate the function
  711.         //
  712.         CodeGenLoopInit(gVariableFlags, &xBranch, &yBranch, &nBranch);
  713.         
  714.         //
  715.         //    If r or theta are used to evaluate the equation, then compute them
  716.         //    from x and y.
  717.         //
  718.         CodeGenRTheta();
  719.         
  720.         //
  721.         //    Generate the code to evaluate the equation.  The equation can be put
  722.         //    in any register.  But make sure it ends up in a real register (not memory).
  723.         //
  724.         result = CodeGenTree(root, 0);
  725.         result = LoadRegister(result, fpResult);
  726.         
  727.         //
  728.         //    Generate loop initialization for any variables that _are not_ used
  729.         //    to evaluate the function.  This just causes the result to be stored
  730.         //    several times in a row, without re-evaluating it.
  731.         //
  732.         CodeGenLoopInit(gVariableFlags ^ (kXMask+kYMask+kNMask), &xBranch, &yBranch, &nBranch);
  733.         
  734.         //
  735.         //    Generate the code to store one result
  736.         //
  737.         CodeGenStoreResult(result);
  738.         FreeRegister(result);
  739.         
  740.         //
  741.         //    Generate the iteration and test parts of the variable loops
  742.         //
  743.         CodeGenLoopEnd(gVariableFlags ^ (kXMask+kYMask+kNMask), xBranch, yBranch, nBranch);
  744.         CodeGenLoopEnd(gVariableFlags, xBranch, yBranch, nBranch);
  745.         
  746.         //
  747.         //    Generate the function epilog -- restore link register and return
  748.         //
  749.         *(gNextInstruction++) = op_mtlr(regSavedLR);        // mtlr r15
  750.         *(gNextInstruction++) = op_blr();                    // blr
  751.     }
  752. }
  753.